/******************************************************
Compile : gcc -O3 -o enumerate enumerate.c
Usage : ./enumerate N
******************************************************/

#include <stdio.h>
#include <stdlib.h>

void print_help ()
{
	printf ("Usage		: ./enumerate N\n");
	printf ("		 (./enumerate 3)\n\n");
	printf ("Description    : This program will enumerate all networks with N nodes and for each network we will check that which circuit is implemented by it.\n");
}

/* calculate the next step for give state under the network using strong inhibition model */
void next_step (int N, int network[N][N], int state[N], int state2[N])
{
	int j, k, flag;

	for (j = 0; j < N; j++)
	{
		flag = 0;
		for (k = 0; k < N; k++)
		{
			if (k == j)
				continue;
			if (state[k] == 1 && network[j][k] == -1)
			{
				state2[j] = 0;
				flag = 1;
				break;
			}
		}

		if (flag == 1)
			continue;

		for (k = 0; k < N; k++)
		{
			if (k == j)
				continue;
			if (state[k] == 1 && network[j][k] == 1)
			{
				state2[j] = 1;
				flag = 1;
				break;
			}
		}

		if (flag == 1)
			continue;

		if (network[j][j] == -1)
			state2[j] = 0;
		else if (network[j][j] == 1)
			state2[j] = 1;
		else if (network[j][j] == 0)
			state2[j] = state[j];
	}
}

void check_circuit (int N, int network[N][N], int state[N], int i)
{
	if (i == N - 1)
	{
		int state2[N], state3[N];

		next_step (N, network, state, state2);
		next_step (N, network, state2, state3);
		printf ("%d", state3[N - 1]);
	}
	else
	{
		state[i] = 1;
		check_circuit (N, network, state, i + 1);
		state[i] = 0;
		check_circuit (N, network, state, i + 1);
	}
}

/* enumerate all networks with N nodes */
void do_enumerate (int N, int network[N][N], int x, int y)
{
	int i, j;

	if (x == N)
	{
		printf ("Candidate Network\n");
		for (i = 0; i < N; i++)
		{
			for (j = 0; j < N; j++)
			{
				if (network[i][j] == 1)
					printf ("g ");
				else if (network[i][j] == -1)
					printf ("r ");
				else if (network[i][j] == 0)
					printf ("n ");
			}
			printf ("\n");
		}
		printf ("Implement circuit ");

		int state[N];

		state[N - 1] = 1;
		check_circuit (N, network, state, 0);

		printf ("\n");
	}
	else
	{
		i = x;
		j = y + 1;
		if (j == N)
		{
			i++;
			j = 0;
		}

		network[x][y] = -1;
		do_enumerate (N, network, i, j);
		network[x][y] = 0;
		do_enumerate (N, network, i, j);
		network[x][y] = 1;
		do_enumerate (N, network, i, j);
	}
}

int main (int argc, char *argv[])
{
	int N;

	if (argc == 1)
	{
		print_help ();
		exit (0);
	}

	N = atoi (argv[1]);

	int network[N][N];

	do_enumerate (N, network, 0, 0);
}
